#ifndef ARVOREC_H_
#define ARVOREC_H_

#include <cstdlib>
#include <iostream>
#include <vector>
#include <iomanip>
#include <exception>

using namespace std;

/**
 * @struct NoC ArvoreC.h "src/estruturas/ArvoreC.h"
 * @brief Classe para controlar o No da ArvoreC.
 * A classe armazena os dados do no atual e aponta para os nos filhos \n
 * da esquerda e da direita. \n
 * Lembrando que como podemos ter vários itens para uma determinada chave \n
 * tratamos o Valor como um vector.
*/
template<class TCHV, class TDADO>
struct NoC
{

	/**
	 * Chave informada.
	 */
	TCHV Chave;

	/**
	 * Valor TDADO.
	 * Temos um vector<TDADO> para armazenar varios itens na mesma chave.
	 */
	vector<TDADO> Valor;

	/**
	 * Itens filhos da direita e esquerda.
	 */
	NoC<TCHV,TDADO> *esq, *dir;

	/**
	 * @fn NoC()
	 * @brief Construtor padrão.
	 * O Construtor já insere null em ambos os nós filhos, \n
	 * para informar que quando criamos um nó ele ainda não tem folhas.
	 */
	NoC()
	{
		esq = dir = NULL;
	}

	/**
	 * @fn NoC(TCHV c, TDADO v, NoC<TCHV, TDADO> *e = NULL, NoC<TCHV, TDADO> *d = NULL)
	 * @brief Construtor por valor.
	 * O Construtor já recebe alguns parâmetros para realizar a contrução do No.
	 * @param c Chave.
	 * @param v valor para inserir no vector.
	 * @param *e No da esquerda.
	 * @param *d No da direita.
	 */
	NoC(TCHV c, TDADO v, NoC<TCHV, TDADO> *e = NULL, NoC<TCHV, TDADO> *d = NULL)
	{
		Chave = c;
		Valor.push_back(v);
		esq = e;
		dir = d;
	}

};

/**
 * @class ArvoreC ArvoreC.h "src/estruturas/ArvoreC.h"
 * @brief Classe para controlar a estrutura de árvore.
 * Essa classe controla a criação da árvore com repetição de itens para \n
 * a mesma chave. Ex: ('Sala 1', 'rafael'), ('Sala 1', 'juliana').
*/
template<class TCHV, class TDADO>
class ArvoreC
{

private:

	/**
	 * A raiz da árvore, o topo.
	 */
	NoC<TCHV, TDADO> *raiz;

public:

	/**
	 * @fn ArvoreC()
	 * @brief Construtor padrão.
	 * O contrutor já informa a raiz como null, \n
	 * informando que quando criado ainda não tem raiz.
	 */
	ArvoreC()
	{
		raiz = NULL;
	}

	/**
	 * @fn ~ArvoreC()
	 * @brief Destrutor
	 * O destrutor limpa todos os itens da chave, \n
	 * utilizando o método Remover recursivamente.
	 */
	virtual ~ArvoreC()
	{
		NoC<TCHV,TDADO> *tmp = raiz;
		while(tmp != NULL)
		{
			tmp = Remover(tmp->Chave, tmp);
		}
	}

	/**
	 * @fn Vazia()
	 * @brief Verifica se a raiz da árvore é nula, \n
	 * se for não existe registro gravado na árvore.
	 * @return true caso sejá uma árvore vazia.
	 */
	bool Vazia()
	{
		return raiz == NULL;
	}

private:

	/*
	 * @fn NoC<TCHV, TDADO> *Insere(TCHV chv, TDADO dado, NoC<TCHV,TDADO> *sub)
	 * @brief Insere novos dados na árvore.
	 * @param chv Chave do No.
	 * @param dado Informação a ser armazenada.
	 * @param sub No atual.
	 */
	NoC<TCHV, TDADO> *Insere(TCHV chv, TDADO dado, NoC<TCHV,TDADO> *sub)
	{

	  if ( sub == NULL )
	  {
	    sub = new NoC<TCHV, TDADO>( chv, dado );
	  }
	  else
	  {

	    if ( chv < sub->Chave )
	       sub->esq = Insere( chv, dado, sub->esq );

	    if ( chv > sub->Chave )
	        sub->dir = Insere( chv, dado, sub->dir );

	    if (chv == sub->Chave)
			sub->Valor.push_back(dado);

	    }

	  return sub;

	}

	/*
	 * @fn NoC<TCHV,TDADO> * Localizar( TCHV chv, NoC<TCHV,TDADO> * subarv )
	 * @brief Localiza um No na árvore.
	 * @param chv Chave do No.
	 * @param subarv No atual.
	 * @return No encontrado.
	 */
	NoC<TCHV,TDADO> * Localizar( TCHV chv, NoC<TCHV,TDADO> * subarv )
	{
	  if ( subarv == NULL ) return NULL;
	  else
	  {
	    if ( chv < subarv->Chave )
	      return Localizar( chv, subarv->esq );
	    else
	    {
	      if ( chv > subarv->Chave )
	        return Localizar( chv, subarv->dir );
	      else
	        return subarv; // No Encontrado
	    }
	  }
	}

	/*
	 * @fn void Imprime( NoC<TCHV,TDADO> *subarv, int nv )
	 * @brief Imprime todas as chaves encontradas na árvore.
	 * @param subarv No atual.
	 * @param nv campo para saber exatamente o espaço para a impressão.
	 */
	void Imprime( NoC<TCHV,TDADO> *subarv, int nv )
	{
	  if ( subarv == NULL ) return;
	  Imprime( subarv->dir, nv + 1 );
	  cout << setw(nv*5) << " " << subarv->Chave << endl;
	  Imprime( subarv->esq, nv + 1 );
	}

	/*
	 * @fn NoC<TCHV,TDADO> *LocalizarMin( NoC<TCHV,TDADO> *subarv )
	 * @brief Localiza o menor No dentro do No especifico.
	 * @param subarv No onde queremos buscar o valor minimo.
	 * @return O ménor No dentro do No informado.
	 */
	NoC<TCHV,TDADO> *LocalizarMin( NoC<TCHV,TDADO> *subarv )
	{
		  if ( subarv->esq != NULL ) subarv = LocalizarMin( subarv->esq );
		  return subarv;

	}

	/*
	 * @fn NoC<TCHV,TDADO> * Remover( TCHV chave, NoC<TCHV,TDADO> * subarv )
	 * @brief Remover um item da árvore utilizando a chave.
	 * @param chave Chave para buscar o item na árvore.
	 * @param subarv No atual.
	 * @return Retorna o No filho, caso o No tenha um.
	 */
	NoC<TCHV,TDADO> * Remover( TCHV chave, NoC<TCHV,TDADO> * subarv )
	{
	  NoC<TCHV,TDADO> * tmp, * filho;
	  if ( subarv == NULL )
	  {
	    return NULL;
	  }
	  else
	  {
	    if ( chave < subarv->Chave )
	    {
	      subarv->esq = Remover( chave, subarv->esq );
	    }
	    else
	    {
	      if ( chave > subarv->Chave )
	      {
	        subarv->dir = Remover( chave, subarv->dir );
	      }
	      else
	      {
	        if ( subarv->esq && subarv->dir )
	        {
	          tmp = LocalizarMin( subarv->dir );
	          subarv->Chave = tmp->Chave;
	          subarv->dir = Remover( subarv->Chave, subarv->dir );
	        }
	        else
	        {
	          tmp = subarv;
	          if ( subarv->esq == NULL ) filho = subarv->dir;
	          if ( subarv->dir == NULL ) filho = subarv->esq;
	          delete tmp;
	          return filho;
	        }
	      }
	    }
	  }
	  return subarv;
	}

	/*
	 * @fn int Altura( NoC<TCHV,TDADO> * subarv )
	 * @brief Quantos itens a árvore têm a partir do no informado.
	 * @param subarv No atual.
	 * @return a altura da árvore.
	 */
	int Altura( NoC<TCHV,TDADO> * subarv )
	{
	  int ae, ad;
	  if ( subarv == NULL ) return 0;
	  if ( subarv->esq == NULL && subarv->dir == NULL ) return 1;
	  ae = Altura( subarv->esq );
	  ad = Altura( subarv->dir );
	  if ( ae > ad )
		return ae + 1;
	  else
	    return ad + 1;
	}

public:

	/**
	 * @fn void Insere(TCHV chave, TDADO dado)
	 * @brief Insere um item na árvore.
	 * @param chave Chave
	 * @param dado Dado
	 */
	void Insere(TCHV chave, TDADO dado)
	{
		raiz = Insere(chave, dado, raiz);
	}

	/**
	 * @fn vector<TDADO> Seleciona(TCHV chave)
	 * @brief Obtem uma lista de valores em uma determinada chave.
	 * @param chave Chave que devemos obter os valores.
	 * @return Um vector com os valores da chave.
	 */
	vector<TDADO> Seleciona(TCHV chave)
	{

		vector<TDADO> valores;

		NoC<TCHV,TDADO> *tmp = Localizar(chave, raiz);

		if(tmp != NULL){
			valores = tmp->Valor;
		}

		return valores;

	}

	/**
	 * @fn void Imprime()
	 * @brief Imprime todas as chaves da árvore.
	 */
	void Imprime()
	{
		Imprime(raiz,1);
	}

	/**
	 * @fn void Remove(TCHV chave)
	 * @brief Deleta um determinado item pela chave informada.
	 * @param chave Chave a ser deletada.
	 */
	void Remove(TCHV chave)
	{
		raiz = Remover(chave, raiz);
	}

	/**
	 * @fn void Altura()
	 * @brief Imprime a quantidade de itens da árvore.
	 */
	void Altura()
	{
		return Altura(raiz);
	}

};

#endif /*ARVOREC_H_*/
